Field of the Invention
The present invention relates to an image search technique using the local feature amounts of an image.
Description of the Related Art
There has been proposed a method of searching for a similar image using the local feature amounts of an image. In this method, first, feature points (local feature points) are extracted from an image (non-patent literature 1). Next, feature amounts (local feature amounts) corresponding to the local feature points are calculated based on the local feature points and image information on the periphery (non-patent literature 2).
In the method using the local feature amounts, each local feature amount is defined as information constructed by a plurality of elements that are rotation-invariant and enlargement/reduction-invariant. This enables a search even when the image is rotated or enlarged/reduced. The local feature amount is generally expressed as a vector. Theory holds that the local feature amounts are rotation-invariant and enlargement/reduction-invariant. In an actual digital image, however, a little change occurs between a local feature amount before rotation or enlargement/reduction processing of the image and a corresponding local feature amount after processing.
In, for example, non-patent literature 2, to extract a local feature amount that is rotation-invariant, a main direction is calculated from the pixel pattern of a local region around the local feature point. When calculating the local feature amount, the local region is rotated based on the main direction, thereby normalizing the direction. To calculate a local feature amount that is enlargement/reduction-invariant, images of different scales are internally generated. Local feature point extraction and local feature amount calculation are performed for each of the images of the scales. In general, the set of a series of internally generated images of different scales is called a scale space.
With the above-described method, a plurality of local feature points are extracted from one image. In an image search using local feature amounts, local feature amounts calculated from the local feature points are compared to do matching. In a voting method (patent literature 1) often used, a feature point similar to a predetermined level or more to the local feature amount of each feature point extracted from a search source image is found by the nearest-neighbor algorithm. If such a feature point exists, one vote is cast to the “image”. The larger the number of votes is, the similar the image is.
In the image search, to efficiently perform matching, image indices are created. In the image indices, local feature amounts are quantized, and a list of images having the feature amount of a certain quantization value is associated with the quantization value and stored in a database. When the image indices are used, a list of images including local feature amounts similar to a certain local feature amount to some extent can quickly be obtained.
In patent literature 2, there is proposed a technique concerning a system that accumulates the contents of a job output from a printing apparatus or the like and allows the job to be tracked. A printed document image, who has printed it, the date/time of printing, and the like are accumulated. When image information of a design or the like has leaked out, the printed document image is searched using the leaked image.
However, several hundreds to several thousands of local feature amounts are extracted from an image. For this reason, when an “image identical to” an image already registered in an image index is registered in an image index again, several hundreds to several thousands of redundant indices are generated. Similarly, when an “image included in” an image already registered in an image index is registered in an image index, redundant indices are generated.
This problem is conspicuous particularly when, for example, a printed document image as in patent literature 2 is to be searched. In, for example, an office, the same document is often printed many times. For this reason, if the above method is applied to such a system, the image indices problematically bloat.
When the indices bloat, the size of indices becomes large. When the indices are redundant, many indices are scanned at the time of a search, and the search speed lowers.
To speed up the search, the indices are often held on a memory. However, if the size of indices is large, arranging them on the physical memory of a computer may be impossible. In this case, the indices are arranged on a virtual memory on an HDD by the function of the OS. Since the speed of referring to the image indices arranged on the HDD is low, the search speed lowers. To avoid this, a physical memory having a large capacity may be prepared. However, this makes the system expensive.